/*
 * [142] 链表中环的入口结点
 *
 * 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null
 *
 *
 * g++ test_cpp.cpp -ggdb -std=c++11
 */

// @lc code=start

// 例子：
/**

head编号0，如果设置prehead,则prehead编号为0，方便分析
 
              ↓--------------←↑
    0 -> 1 -> 2 -> 3 -> 4 -> 5
slow: 0 → 1 → 2 → 3 → 4
fast: 0 → 2 → 4 → 2 → 4
无环部分路径长度2，有环部分路径长度4
相遇后，fast比slow多走了有环部分的路径长度4，故在距起点长度4的结点4处相遇
slow继续行进路径长度2就能走完整个链表即到入口，在开头设置一指针entry，则也行进路径长度2到入口与slow相遇

**/

#include <algorithm>
#include <iostream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

// Definition for singly-linked list.
struct ListNode
{
  int val;
  struct ListNode* pnext;
  ListNode(int x) : val(x), pnext(NULL) {}
};

class Solution
{
 public:
  /*ListNode *detectCycle(ListNode *head) {
        if(!head) return NULL;
        ListNode* fast=head, *slow=head;
        while(fast!=slow)
        {
          fast=fast->next->next;
          slow=slow->next;
          if(slow==head&&slow&&fast)
          {
            slow=head;
          }
          else if(!slow&&!fast) return NULL;
        }
    }*/

  ListNode* detectCycle(ListNode* head)
  {
    auto fast = head, slow = head;
    while (fast)
    {
      // 保证fast!=null，才去访问它的next
      fast = fast->next;
      slow = slow->next;
      // 快指针快走
      if (fast)
        fast = fast->next;
      else
        break;

      if (fast == slow)
      {
        // 第一次相遇后，slow回到原点
        slow = head;
        while (slow != fast)
        {
          fast = fast->next;
          slow = slow->next;
        }

        return slow;
      }
    }
    return NULL;
  }
  // 在首结点head之前是头结点prehead
  ListNode* detectCycle(ListNode* head)
  {
    // 防御性编程
    if (head == nullptr || head->pnext == nullptr) return nullptr;
    ListNode *slow, *fast, *entry;
    slow = fast = entry = head;

    // 如果有环，fast不可能为nullptr，无环时，fast会运行到末尾null,退出循环
    while (fast && fast->pnext)
    {
      slow = slow->pnext;
      fast = fast->pnext->pnext;
      // 如果有环找环入口
      if (slow == fast)
      {
        // slow从环入口的位置继续走无环结点数n1, entry从起点走n1，两者在环入口相遇
        while (slow != entry)
        {
          slow = slow->pnext;
          entry = entry->pnext;
        }
        // 退出while即相遇了，返回入口的指针
        return slow;
      }
    }
    return nullptr;
  }
};

int main()
{
  class Solution solute;
  ListNode* prehead = new ListNode(-1);

  ListNode* head = new ListNode(1);
  prehead->pnext = head;

  ListNode* node2 = new ListNode(2);
  head->pnext = node2;
  node2->pnext = nullptr;

  ListNode* node3 = new ListNode(2);
  node2->pnext = node3;
  node3->pnext = nullptr;

  ListNode* node4 = new ListNode(3);
  node3->pnext = node4;
  node4->pnext = nullptr;

  ListNode* node5 = new ListNode(5);
  node4->pnext = node5;
  node5->pnext = node2;

  ListNode* entry = solute.detectCycle(head);

  return 0;
}

// @lc code=end
